159D - Palindrome pairs - CodeForces Solution

s = input()
n = len(s)
L, R = [0]*n, [0]*n
for i in range(n):
    for j in (i-1, i):
        k = i
        while j >= 0 and k < n and s[j] == s[k]:
            L[k] += 1
            R[j] += 1
            j -= 1
            k += 1
ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += L[i]*R[j]
print(ans)